home *** CD-ROM | disk | FTP | other *** search
/ Amiga Collections: Taifun / Taifun 054 (1988-05-15)(Ossowski, Stefan)(DE)(PD).zip / Taifun 054 (1988-05-15)(Ossowski, Stefan)(DE)(PD).adf / MRBackup / MRBackup2.0 / Compress.c < prev    next >
C/C++ Source or Header  |  1988-04-09  |  22KB  |  962 lines
  1. /* MRBackup: File Compression/Decompression Routines
  2.  * Filename:    Compress.c
  3.  * History:        (most recent change first)
  4.  *
  5.  * 09/19/87 -MRR- Fixed bugs in decompression routine, introduced by
  6.  *                new buffering scheme.
  7.  *
  8.  * 09/04/87 -MRR- This package now uses MRBackup's buffer to hold the
  9.  *                compressed data and uses AmigaDOS I/O.
  10.  */
  11.  
  12. /* 
  13.  * Compress.c - data compression/decompression routines.
  14.  * This is an adaptation of the public domain Un*x compress v4.0.
  15.  */
  16.  
  17. #include "MRBackup.h"
  18.  
  19. #define    min(a,b)    ((a>b) ? b : a)
  20. #define INBUFSIZE    4L*1024L        /* input buffer size */
  21.  
  22. #ifdef DEBUG
  23. #define DBG(x) x
  24. #else
  25. #define DBG(x)
  26. #endif
  27.  
  28. extern int errno;
  29.  
  30. /*
  31.  * Set USERMEM to the maximum amount of physical user memory available
  32.  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
  33.  * for compression.
  34.  *
  35.  * SACREDMEM is the amount of physical memory saved for others; compress
  36.  * will hog the rest.
  37.  */
  38. #ifndef SACREDMEM
  39. #define SACREDMEM    0
  40. #endif
  41.  
  42. #ifndef USERMEM
  43. # define USERMEM     450000            /* default user memory */
  44. #endif
  45.  
  46. # define MAXFILES       100            /* arbitrary maximum - see note below */
  47. # define BITS        12                /* > 12 crashes system (?) */
  48. # undef USERMEM
  49. long    filesize();
  50. char   *scdir();
  51.  
  52. #ifdef USERMEM
  53. # if USERMEM >= (433484+SACREDMEM)
  54. #  define PBITS    16
  55. # else
  56. #  if USERMEM >= (229600+SACREDMEM)
  57. #   define PBITS    15
  58. #  else
  59. #   if USERMEM >= (127536+SACREDMEM)
  60. #    define PBITS    14
  61. #   else
  62. #    if USERMEM >= (73464+SACREDMEM)
  63. #     define PBITS    13
  64. #    else
  65. #     define PBITS    12
  66. #    endif
  67. #   endif
  68. #  endif
  69. # endif
  70. # undef USERMEM
  71. #endif                                /* USERMEM */
  72.  
  73. #ifdef PBITS                        /* Preferred BITS for this memory size */
  74. # ifndef BITS
  75. #  define BITS PBITS
  76. # endif BITS
  77. #endif                                /* PBITS */
  78.  
  79. #if BITS == 16
  80. # define HSIZE    69001L                /* 95% occupancy */
  81. #endif
  82. #if BITS == 15
  83. # define HSIZE    35023L                /* 94% occupancy */
  84. #endif
  85. #if BITS == 14
  86. # define HSIZE    18013L                /* 91% occupancy */
  87. #endif
  88. #if BITS == 13
  89. # define HSIZE    9001L                /* 91% occupancy */
  90. #endif
  91. #if BITS <= 12
  92. # define HSIZE    5003L                /* 80% occupancy */
  93. #endif
  94.  
  95. /*
  96.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  97.  */
  98. #if BITS > 15
  99. typedef long int    code_int;
  100. #else
  101. typedef int     code_int;
  102. #endif
  103.  
  104. #ifdef SIGNED_COMPARE_SLOW
  105. typedef unsigned long int count_int;
  106. typedef unsigned short int count_short;
  107. #else
  108. typedef long int    count_int;
  109. #endif
  110.  
  111. #ifdef NO_UCHAR
  112. typedef char    char_type;
  113. #else
  114. typedef unsigned char   char_type;
  115. #endif                                /* UCHAR */
  116. char_type magic_header[]= {
  117.     "\037\235" 
  118. };                                    /* 1F 9D */
  119.  
  120. /* Defines for third byte of header */
  121. #define BIT_MASK    0x1f
  122. #define BLOCK_MASK    0x80
  123. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  124.    a fourth header byte (for expansion).
  125. */
  126. #define INIT_BITS 9                    /* initial number of bits/code */
  127.  
  128. /*
  129.  * compress.c - File compression ala IEEE Computer, June 1984.
  130.  *
  131.  * Authors:    
  132.  *        Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  133.  *        Jim McKie            (decvax!mcvax!jim)
  134.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  135.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  136.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  137.  *        Joe Orost            (decvax!vax135!petsd!joe)
  138.  *        Mark R. Rinfret        (mods) (mark@unisec.USI.COM)
  139.  */
  140.  
  141. static unsigned debug = 0;            /* true => execute debug code */
  142. static unsigned endInput;            /* true => input file exhausted */
  143. static int n_bits;                    /* number of bits/code */
  144. static int maxbits = BITS;            /* user settable max # bits/code */
  145. static code_int maxcode;            /* maximum code, given n_bits */
  146. static code_int maxmaxcode = 1 << BITS;    /* NEVER generate this code */
  147. #define MAXCODE(n_bits)    ((1 << (n_bits)) - 1)
  148.  
  149. static count_int htab [HSIZE];
  150. static USHORT codetab [HSIZE];
  151. #define htabof(i)        htab[i]
  152. #define codetabof(i)    codetab[i]
  153.  
  154. static code_int hsize = HSIZE;        /* for dynamic table sizing */
  155. static count_int fsize;
  156.  
  157. static struct FileHandle *infile, *outfile;
  158. static char iname[256], oname[256];
  159. static UBYTE inbuf[INBUFSIZE], *inbufptr;
  160. static LONG inbufsize;
  161. static UBYTE *outbufptr;
  162.  
  163. /*
  164.  * To save much memory, we overlay the table used by compress() with those
  165.  * used by decompress().  The tab_prefix table is the same size and type
  166.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  167.  * get this from the beginning of htab.  The output stack uses the rest
  168.  * of htab, and contains characters.  There is plenty of room for any
  169.  * possible stack (stack used to be 8000 characters).
  170.  */
  171.  
  172. #define tab_prefixof(i)    codetabof(i)
  173. #define tab_suffixof(i)    ((char_type *)(htab))[i]
  174. #define de_stack        ((char_type *)&tab_suffixof(1<<BITS))
  175.  
  176. static code_int free_ent = 0;        /* first unused entry */
  177. static int status = 0;
  178.  
  179. code_int getcode();
  180.  
  181. static int nomagic = 0;                /* Use a 3-byte magic number header,
  182.                                        unless old file */
  183. static int zcat_flg = 0;            /* Write output on stdout, suppress
  184.                                        messages */
  185. static int quiet = 1;                /* don't tell me about compression */
  186.  
  187. /*
  188.  * block compression parameters -- after all codes are used up,
  189.  * and compression rate changes, start over.
  190.  */
  191. static int block_compress = BLOCK_MASK;
  192. static int clear_flg = 0;
  193. static long int ratio = 0;
  194. #define CHECK_GAP 10000                /* ratio check interval */
  195. static count_int checkpoint = CHECK_GAP;
  196. /*
  197.  * the next two codes should not be changed lightly, as they must not
  198.  * lie within the contiguous general code space.
  199.  */
  200. #define FIRST    257                    /* first free entry */
  201. #define    CLEAR    256                    /* table clear output code */
  202.  
  203. static int force = 0;
  204. static char ofname [100];
  205. #ifdef DEBUG
  206. static int verbose = 0;
  207. #endif                                /* DEBUG */
  208. int     (*bgnd_flag)();
  209.  
  210. static int do_decomp = 0;
  211. static int offset;
  212. static LONG in_count;                /* length of input */
  213. static LONG bytes_out;                /* length of compressed output */
  214. static LONG out_count;                /* # of codes output (for debugging) */
  215. static LONG outbufcount;            /* # bytes in output buffer */
  216. ^L
  217. /*****************************************************************
  218.  *
  219.  * Algorithm from "A Technique for High Performance Data Compression",
  220.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  221.  *
  222.  * Algorithm:
  223.  * Modified Lempel-Ziv method (LZW).  Basically finds common
  224.  * substrings and replaces them with a variable size code.  This is
  225.  * deterministic, and can be done on the fly.  Thus, the decompression
  226.  * procedure needs no input table, but tracks the way the table was built.
  227.  */
  228.  
  229. static void
  230. comp_init()
  231. {
  232.     if(maxbits < INIT_BITS)
  233.         maxbits = INIT_BITS;
  234.     if (maxbits > BITS)
  235.         maxbits = BITS;
  236.     maxmaxcode = 1 << maxbits;
  237.     outbufcount = 0;
  238.     outbufptr = buffer;
  239. }
  240.  
  241.  
  242. /*
  243.  * compress "from" to "to"
  244.  *
  245.  * Algorithm:  use open addressing double hashing (no chaining) on the 
  246.  * prefix code / next character combination.  We do a variant of Knuth's
  247.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  248.  * secondary probe.  Here, the modular division first probe is gives way
  249.  * to a faster exclusive-or manipulation.  Also do block compression with
  250.  * an adaptive reset, whereby the code table is cleared when the compression
  251.  * ratio decreases, but after the table fills.  The variable-length output
  252.  * codes are re-sized at this point, and a special CLEAR code is generated
  253.  * for the decompressor.  Late addition:  construct the table according to
  254.  * file size for noticeable speed improvement on small files.  Please direct
  255.  * questions about this implementation to ames!jaw.
  256.  */
  257.  
  258. int 
  259. compress(from, to)
  260.     char *from, *to;
  261. {
  262.     register long   fcode;
  263.     register code_int i = 0;
  264.     register int    c;
  265.     register code_int ent;
  266.     register int    disp;
  267.     register code_int hsize_reg;
  268.     register int    hshift;
  269.     char *s;
  270.     char *err_msg[256];
  271.  
  272.     comp_init();
  273.     inbufsize = 0;
  274.     endInput = false;
  275.  
  276.     /* 
  277.      * tune hash table size for small files -- ad hoc,
  278.      * but the sizes match earlier #defines, which
  279.      * serve as upper bounds on the number of output codes. 
  280.      */
  281.         hsize = HSIZE;
  282.         if (fsize < (1L << 12))
  283.             hsize = min (5003L,HSIZE );
  284.         else 
  285.             if (fsize < (1L << 13))
  286.                 hsize = min (9001L,HSIZE );
  287.             else 
  288.                 if (fsize < (1L << 14))
  289.                     hsize = min (18013L,HSIZE );
  290.                 else 
  291.                     if (fsize < (1L << 15))
  292.                         hsize = min (35023L,HSIZE );
  293.                     else 
  294.                         if (fsize < 47000L )
  295.                             hsize = min (50021L,HSIZE );
  296.  
  297.     if (!(infile = Open(from, MODE_OLDFILE))) {
  298.         return IoErr();
  299.     }
  300.  
  301.     if (!(outfile = Open(to, MODE_NEWFILE))) {
  302.         status = IoErr();
  303.         Close(infile);
  304.         return status;
  305.     }
  306.  
  307.     if (nomagic == 0){
  308.         putcbuf(magic_header[0]);
  309.         putcbuf(magic_header[1]);
  310.         putcbuf((char)(maxbits | block_compress));
  311.         if(status) {
  312. cleanup:
  313.             Close(infile);
  314.             Close(outfile);
  315.             return status;
  316.         }
  317.     }
  318.  
  319.     offset = 0;
  320.     bytes_out = 3;                    /* includes 3-byte header mojo */
  321.     out_count = 0;
  322.     clear_flg = 0;
  323.     ratio = 0L;
  324.     in_count = 1;
  325.     checkpoint = CHECK_GAP;
  326.     maxcode = MAXCODE(n_bits = INIT_BITS);
  327.     free_ent = ((block_compress)?FIRST :256 );
  328.  
  329.     ent = ReadChar();
  330.  
  331.     hshift = 0;
  332.     for (fcode = (long) hsize; fcode < 65536L; fcode *= 2L )
  333.         hshift++;
  334.     hshift = 8 - hshift;            /* set hash code range bound */
  335.  
  336.     hsize_reg = hsize;
  337.     cl_hash((count_int)hsize_reg);    /* clear hash table */
  338.  
  339.     /*while ((c = getc(infile))!= EOF ){*/
  340.     while ( ( c = ReadChar() ) != EOF) {
  341.         in_count++;
  342.         fcode = (long)(((long)c << maxbits)+ ent);
  343.         i = ((c << hshift)^ ent);    /* xor hashing */
  344.  
  345.         if (htabof (i)== fcode ){
  346.             ent = codetabof (i);
  347.             continue;
  348.         }
  349.         else 
  350.             if ((long)htabof (i)< 0 )/* empty slot */
  351.                 goto nomatch;
  352.         disp = hsize_reg - i;        /* secondary hash (after G. Knott) */
  353.         if (i == 0 )
  354.             disp = 1;
  355. probe: 
  356.         if ((i -= disp)< 0 )
  357.             i += hsize_reg;
  358.  
  359.         if (htabof (i)== fcode ){
  360.             ent = codetabof (i);
  361.             continue;
  362.         }
  363.         if ((long)htabof (i)> 0 )
  364.             goto probe;
  365. nomatch: 
  366.         output ((code_int)ent );
  367.         out_count++;
  368.         ent = c;
  369.         if (free_ent < maxmaxcode ){
  370.             codetabof (i)= free_ent++;/* code -> hashtable */
  371.             htabof (i)= fcode;
  372.         }
  373.         else 
  374.             if ((count_int)in_count >= checkpoint && block_compress )
  375.                 cl_block ();
  376.     }
  377.  /* 
  378.   * Put out the final code.
  379.   */
  380.     output((code_int)ent );
  381.     out_count++;
  382.     output((code_int)-1 );
  383.  
  384.  /* 
  385.   * Print out stats on stderr
  386.   */
  387.     if(zcat_flg == 0 && !quiet){
  388. #ifdef DEBUG
  389.         fprintf(stderr,
  390.             "%ld chars in, %ld codes (%ld bytes) out, compression factor: ",
  391.             in_count,out_count,bytes_out );
  392.         prratio(stderr,in_count,bytes_out );
  393.         fprintf(stderr,"\n");
  394.         fprintf(stderr,"\tCompression as in compact: " );
  395.         prratio(stderr,in_count-bytes_out,in_count );
  396.         fprintf(stderr,"\n");
  397.         fprintf(stderr,"\tLargest code (of last block) was %d (%d bits)\n",
  398.                 free_ent - 1,n_bits );
  399. #endif                                /* DEBUG */
  400.     }
  401.     flushbuf();                        /* dump the last block */
  402.     if(bytes_out > in_count)        /* exit(2) if no savings */
  403.         status = 2;
  404.     goto cleanup;
  405. }
  406.  
  407. /*****************************************************************
  408.  * TAG( output )
  409.  *
  410.  * Output the given code.
  411.  * Inputs:
  412.  *     code:    A n_bits-bit integer.  If == -1, then EOF.  This assumes
  413.  *        that n_bits =< (long)wordsize - 1.
  414.  * Outputs:
  415.  *     Outputs code to the file.
  416.  * Assumptions:
  417.  *    Chars are 8 bits long.
  418.  * Algorithm:
  419.  *     Maintain a BITS character long buffer (so that 8 codes will
  420.  * fit in it exactly).  Use the VAX insv instruction to insert each
  421.  * code in turn.  When the buffer fills up empty it and start over.
  422.  */
  423.  
  424. static char     buf[BITS];
  425.  
  426. char_type lmask[9]= {
  427.     0xff,0xfe,0xfc,0xf8,0xf0,0xe0,0xc0,0x80,0x00
  428. };
  429. char_type rmask[9]= {
  430.     0x00,0x01,0x03,0x07,0x0f,0x1f,0x3f,0x7f,0xff
  431. };
  432.  
  433. output(code)
  434.     code_int code;
  435. {
  436. #ifdef DEBUG
  437.     static int col = 0;
  438. #endif                                /* DEBUG */
  439.  
  440.     register int r_off = offset, bits = n_bits;
  441.     register char * bp = buf;
  442.     int count;
  443.  
  444. #ifdef DEBUG
  445.     if (verbose )
  446.         fprintf(stderr,"%5d%c",code,
  447.                 (col+=6)>= 74 ?(col = 0,'\n'):' ' );
  448. #endif                                /* DEBUG */
  449.     if (code >= 0 ){
  450. /* 
  451.  * byte/bit numbering on the VAX is simulated by the following code
  452.  */
  453.     /* 
  454.      * Get to the first byte.
  455.      */
  456.         bp += (r_off >> 3);
  457.         r_off &= 7;
  458.     /* 
  459.      * Since code is always >= 8 bits, only need to mask the first
  460.      * hunk on the left.
  461.      */
  462.         *bp = (*bp & rmask[r_off])| (code << r_off)& lmask[r_off];
  463.         bp++;
  464.         bits -= (8 - r_off);
  465.         code >>= 8 - r_off;
  466.  
  467.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  468.  
  469.         if (bits >= 8 ){
  470.             *bp++= code;
  471.             code >>= 8;
  472.             bits -= 8;
  473.         }
  474.     /* Last bits. */
  475.         if(bits)
  476.             *bp = code;
  477.         offset += n_bits;
  478.         if (offset == (n_bits << 3)){
  479.             bp = buf;
  480.             bits = n_bits;
  481.             bytes_out += bits;
  482.             do
  483.                 putcbuf(*bp++);
  484.             while(--bits);
  485.             offset = 0;
  486.         }
  487.  
  488.     /* 
  489.      * If the next entry is going to be too big for the code size,
  490.      * then increase it, if possible.
  491.      */
  492.         if (free_ent > maxcode || (clear_flg > 0)){
  493.         /* 
  494.          * Write the whole buffer, because the input side won't
  495.          * discover the size increase until after it has read it.
  496.          */
  497.             if (offset > 0 ){
  498.                 putmcbuf(buf, n_bits);
  499.                 if (status) return 1;
  500.                 bytes_out += n_bits;
  501.             }
  502.             offset = 0;
  503.  
  504.             if (clear_flg ){
  505.                 maxcode = MAXCODE (n_bits = INIT_BITS);
  506.                 clear_flg = 0;
  507.             }
  508.             else {
  509.                 n_bits++;
  510.                 if (n_bits == maxbits )
  511.                     maxcode = maxmaxcode;
  512.                 else
  513.                     maxcode = MAXCODE(n_bits);
  514.             }
  515. #ifdef DEBUG
  516.             if (debug ){
  517.                 fprintf(stderr,"\nChange to %d bits\n",n_bits );
  518.                 col = 0;
  519.             }
  520. #endif                                /* DEBUG */
  521.         }
  522.     }
  523.     else {
  524.     /* 
  525.      * At EOF, write the rest of the buffer.
  526.      */
  527.          count = (offset + 7) / 8;
  528.         if (offset > 0 ) {
  529.             putmcbuf(buf, count);
  530.         }
  531.         bytes_out += count;
  532.         offset = 0;
  533.  
  534. #ifdef DEBUG
  535.         if (verbose )
  536.             fprintf(stderr,"\n" );
  537. #endif                                /* DEBUG */
  538.  
  539.         if(status) 
  540.             return 1;
  541.     }
  542.     return 0;
  543. }
  544.  
  545. /*
  546.  * Decompress infile to outfile.  This routine adapts to the codes in the
  547.  * file building the "string" table on-the-fly; requiring no table to
  548.  * be stored in the compressed file.  The tables used herein are shared
  549.  * with those of the compress() routine.  See the definitions above.
  550.  */
  551.  
  552. int
  553. decompress(from, to)
  554.     char *from, *to;
  555. {
  556.     register    char_type *stackp;
  557.     register     int finchar;
  558.     register    code_int code,oldcode,incode;
  559.     int c1, c2;
  560.  
  561.     outbufcount = 0;
  562.     outbufptr = buffer;
  563.     inbufsize = 0;
  564.     endInput = false;
  565.  
  566.     if (!(infile = Open(from, MODE_OLDFILE))) {
  567.         status = IoErr();
  568.         return status;
  569.     }
  570.     if (!(outfile = Open(to, MODE_NEWFILE))) {
  571.         status = IoErr();
  572.         Close(infile);
  573.         return status;
  574.     }
  575.  
  576.     if (nomagic == 0){
  577.         if (((c1 = ReadChar()) != (magic_header[0] & 0xFF)) || 
  578.             ((c2 = ReadChar()) != (magic_header[1] & 0xFF))) {
  579.             status = -2;            /* unknown format */
  580.             sprintf(conmsg, "Bad header? c1/c2 == %02x/%02x\n",c1,c2);
  581.             WriteConsole(conmsg);
  582. cleanup:
  583.             Close(infile);
  584.             Close(outfile);
  585.             return status;
  586.         }
  587.         maxbits = ReadChar();        /* set -b from file */
  588.         block_compress = maxbits & BLOCK_MASK;
  589.         maxbits &= BIT_MASK;
  590.         maxmaxcode = 1 << maxbits;
  591.         if(maxbits > BITS){
  592.             status = -3;            /* too many bits to handle */
  593.             goto cleanup;
  594.         }
  595.     }
  596.  /* 
  597.   * As above, initialize the first 256 entries in the table.
  598.   */
  599.     maxcode = MAXCODE(n_bits = INIT_BITS);
  600.     for (code = 255; code >= 0; code--){
  601.         tab_prefixof(code) = 0;
  602.         tab_suffixof(code) = (char_type)code;
  603.     }
  604.     free_ent = ((block_compress) ? FIRST : 256 );
  605.  
  606.     finchar = oldcode = getcode();
  607.     if ( status )                    /* EOF already? */
  608.         goto cleanup;
  609.  
  610.     putcbuf(finchar);                /* first code must be 8 bits = char */
  611.     if(status)                        /* Crash if can't write */
  612.         goto cleanup;
  613.  
  614.     stackp = de_stack;
  615.  
  616.     while ((code = getcode()) > -1 ){
  617.         if ((code == CLEAR) && block_compress ){
  618.             for (code = 255; code >= 0; code--)
  619.                 tab_prefixof(code) = 0;
  620.             clear_flg = 1;
  621.             free_ent = FIRST - 1;
  622.             if ((code = getcode ()) == -1 )/* O, untimely death! */
  623.                 break ;
  624.         }
  625.         incode = code;
  626.     /* 
  627.      * Special case for KwKwK string.
  628.      */
  629.         if (code >= free_ent ){
  630.             *stackp++ = finchar;
  631.             code = oldcode;
  632.         }
  633.  
  634.     /* 
  635.      * Generate output characters in reverse order
  636.      */
  637.         while (code >= 256 ){
  638.             *stackp++= tab_suffixof(code);
  639.             code = tab_prefixof(code);
  640.         }
  641.         *stackp++ = finchar = tab_suffixof(code);
  642.  
  643.     /* 
  644.      * And put them out in forward order
  645.      */
  646.         do
  647.             putcbuf(*--stackp);
  648.         while (stackp > de_stack );
  649.  
  650.     /* 
  651.      * Generate the new entry.
  652.      */
  653.         if ( ( code = free_ent ) < maxmaxcode ){
  654.             tab_prefixof(code) = (unsigned short) oldcode;
  655.             tab_suffixof(code) = finchar;
  656.             free_ent = code+1;
  657.         }
  658.     /* 
  659.      * Remember previous code.
  660.      */
  661.         oldcode = incode;
  662.     }
  663.     flushbuf();
  664.     goto cleanup;
  665. }
  666.  
  667. /*****************************************************************
  668.  * Read one code from the standard input.  If EOF, return -1.
  669.  * Inputs:
  670.  *             infile
  671.  * Outputs:
  672.  *             code or -1 is returned.
  673.  */
  674.  
  675. code_int
  676. getcode(){
  677.  /* 
  678.   * On the VAX, it is important to have the register declarations
  679.   * in exactly the order given, or the asm will break.
  680.   */
  681.     register code_int code;
  682.     static int offset = 0, size = 0;
  683.     static char_type buf[BITS];
  684.     register int r_off,bits;
  685.     register char_type *bp = buf;
  686.     int c;
  687.  
  688.     if (clear_flg > 0 || offset >= size || free_ent > maxcode ){
  689.     /* 
  690.      * If the next entry will be too big for the current code
  691.      * size, then we must increase the size.  This implies reading
  692.      * a new buffer full, too.
  693.      */
  694.         if (free_ent > maxcode ){
  695.             n_bits++;
  696.             if (n_bits == maxbits )
  697.                 maxcode = maxmaxcode;    /* won't get any bigger now */
  698.             else
  699.                 maxcode = MAXCODE(n_bits);
  700.         }
  701.         if (clear_flg > 0) {
  702.             maxcode = MAXCODE (n_bits = INIT_BITS);
  703.             clear_flg = 0;
  704.         }
  705.         size = 0;
  706.         while (size < n_bits) {
  707.             if ((c = ReadChar()) == EOF || status ) break;
  708.             buf[size++] = c;
  709.         }
  710.         if (size == 0  || status) {
  711.             return EOF;                /* end of file */
  712.         }
  713.  
  714.         offset = 0;
  715.  
  716.         /* Round size down to integral number of codes */
  717.  
  718.         size = (size << 3)- (n_bits - 1);
  719.     }
  720.     r_off = offset;
  721.     bits = n_bits;
  722.  /* 
  723.   * Get to the first byte.
  724.   */
  725.     bp += (r_off >> 3);
  726.     r_off &= 7;
  727.  
  728.  /* Get first part (low order bits) */
  729.  
  730. #ifdef NO_UCHAR
  731.     code = ((*bp++ >> r_off)& rmask[8 - r_off]) & 0xff;
  732. #else
  733.     code = (*bp++ >> r_off);
  734. #endif                                /* NO_UCHAR */
  735.     bits -= (8 - r_off);
  736.     r_off = 8 - r_off;                /* now, offset into code word */
  737.  
  738.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  739.  
  740.     if (bits >= 8 ){
  741. #ifdef NO_UCHAR
  742.         code |= (*bp++ & 0xff) << r_off;
  743. #else
  744.         code |= *bp++ << r_off;
  745. #endif                                /* NO_UCHAR */
  746.         r_off += 8;
  747.         bits -= 8;
  748.     }
  749.  /* high order bits. */
  750.     code |= (*bp & rmask[bits]) << r_off;
  751.     offset += n_bits;
  752.  
  753.     return code;
  754. }
  755.  
  756. #ifndef AZTEC_C
  757. char *
  758. rindex(s,c)
  759.     register char *s,c;
  760. {
  761.     char   *p;
  762.     for (p = NULL;*s;s++)
  763.         if (*s == c)
  764.             p = s;
  765.     return(p);
  766. }
  767. #endif
  768.  
  769. /*
  770.  * This routine returns 1 if we are running in the foreground and stderr
  771.  * is a tty.
  772.  */
  773. foreground()
  774. {
  775.      /* I don't know how to test for background, yet. */
  776.     return (isatty(2));
  777. }
  778.  
  779. onintr()
  780. {
  781.     unlink ( ofname );
  782.     exit (1 );
  783. }
  784.  
  785. /* wild pointer -- assume bad input */
  786.  
  787. oops ()
  788. {                            
  789.     if ( do_decomp == 1 )
  790.         fprintf (stderr,"uncompress: corrupt input\n" );
  791.     unlink ( ofname );
  792.     exit ( 1 );
  793. }
  794.  
  795. /* table clear for block compress */
  796.  
  797. cl_block ()
  798. {                        
  799.     register long int rat;
  800.  
  801.     checkpoint = in_count + CHECK_GAP;
  802. #ifdef DEBUG
  803.     if (debug ){
  804.         fprintf (stderr,"count: %ld, ratio: ",in_count );
  805.         prratio (stderr,in_count,bytes_out );
  806.         fprintf (stderr,"\n");
  807.     }
  808. #endif                                /* DEBUG */
  809.  
  810.     if(in_count > 0x007fffff){        /* shift will overflow */
  811.         rat = bytes_out >> 8;
  812.         if(rat == 0){                /* Don't divide by zero */
  813.             rat = 0x7fffffff;
  814.         }
  815.         else {
  816.             rat = in_count / rat;
  817.         }
  818.     }
  819.     else {
  820.         rat = (in_count << 8) / bytes_out; /* 8 fractional bits */
  821.     }
  822.     if (rat > ratio ){
  823.         ratio = rat;
  824.     }
  825.     else {
  826.         ratio = 0;
  827.         cl_hash ((count_int)hsize );
  828.         free_ent = FIRST;
  829.         clear_flg = 1;
  830.         output ((code_int)CLEAR );
  831. #ifdef DEBUG
  832.         if(debug)
  833.             fprintf (stderr,"clear\n" );
  834. #endif                                /* DEBUG */
  835.     }
  836. }
  837.  
  838. cl_hash(hsize)                        /* reset code table */
  839. register count_int hsize;
  840. {
  841.     register count_int *htab_p = htab+hsize;
  842.     register long i;
  843.     register long m1 = -1;
  844.  
  845.     i = hsize - 16;
  846.     do {                            /* might use Sys V memset(3) here */
  847.         *(htab_p-16)= m1;
  848.         *(htab_p-15)= m1;
  849.         *(htab_p-14)= m1;
  850.         *(htab_p-13)= m1;
  851.         *(htab_p-12)= m1;
  852.         *(htab_p-11)= m1;
  853.         *(htab_p-10)= m1;
  854.         *(htab_p-9)= m1;
  855.         *(htab_p-8)= m1;
  856.         *(htab_p-7)= m1;
  857.         *(htab_p-6)= m1;
  858.         *(htab_p-5)= m1;
  859.         *(htab_p-4)= m1;
  860.         *(htab_p-3)= m1;
  861.         *(htab_p-2)= m1;
  862.         *(htab_p-1)= m1;
  863.         htab_p -= 16;
  864.     } while ((i -= 16) >= 0);
  865.  
  866.     for (i += 16; i > 0; i--)
  867.         *--htab_p = m1;
  868. }
  869. #ifdef DEBUG
  870. prratio(stream,num,den)
  871. FILE *stream;
  872. long int    num,den;
  873. {
  874.     register int    q;                /* Doesn't need to be long */
  875.  
  876.     if(num > 214748L){                /* 2147483647/10000 */
  877.         q = num / (den / 10000L);
  878.     }
  879.     else {
  880.         q = (10000L*num)/ den;        /* Long calculations, though */
  881.     }
  882.     if (q < 0){
  883.         putc('-',stream);
  884.         q = -q;
  885.     }
  886.     fprintf(stream,"%d.%02d%%",q / 100,q % 100);
  887. }
  888. #endif
  889.  
  890. /* Flush the output buffer. */
  891.  
  892. flushbuf()
  893. {
  894.     if (Write(outfile, buffer, outbufcount) != outbufcount) {
  895.         status = IoErr();
  896.     }
  897.     outbufcount = 0;
  898.     outbufptr = buffer;
  899. }
  900.  
  901. /* Put a character into the output buffer.  If the buffer is full,
  902.  * output the buffer, then reset its count to zero.
  903.  * Called with:
  904.  *        c:        character to be output
  905.  * Returns:
  906.  *        status code (0 => OK)
  907.  */
  908.  
  909. int
  910. putcbuf(c)
  911. {
  912.     if (outbufcount >= bufSize)     flushbuf();
  913.     *outbufptr++ = c;
  914.     ++outbufcount;
  915.     return status;
  916. }
  917.  
  918. /* Put multiple characters in the output buffer.
  919.  * Called with:
  920.  *        buf:        address of character array
  921.  *        count:        number of characters to output
  922.  * Returns:
  923.  *        status 
  924.  */
  925.  
  926. putmcbuf(buf, count)
  927.     char *buf; int count;
  928. {
  929.     for (; count; --count)     if ( putcbuf( *buf++ ) ) break;
  930.     return status;
  931. }
  932.  
  933. /* Read 1 character from the input file.
  934.  * Returns:
  935.  *   character code or -1 (EOF)
  936.  */
  937.  
  938. int
  939. ReadChar()
  940. {
  941. again:
  942.     if (inbufsize == 0) {
  943.         if (endInput)
  944.             return EOF;
  945.  
  946.         if ((inbufsize = Read(infile, inbuf, INBUFSIZE)) == -1L) {
  947.             status = IoErr();
  948.             return EOF;
  949.         }
  950.  
  951.         inbufptr = inbuf;                /* reset buffer pointer */
  952.  
  953.         if (inbufsize < INBUFSIZE) {
  954.             endInput = true;
  955.             goto again;
  956.         }
  957.     }
  958.     ++in_count;
  959.     --inbufsize;
  960.     return (*inbufptr++);
  961. }
  962.